/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Neighbors []*Node
 * }
 */

func cloneGraph(node *Node) *Node {
    visited := make(map[*Node]*Node)
    return dfs(node, visited)
}

func dfs(node *Node, visited map[*Node]*Node) *Node {
    if node == nil {
        return nil
    }
    if _, ok := visited[node]; ok {
        return visited[node]
    }

    newNode := &Node{Val: node.Val}
    visited[node] = newNode

    for _, neighbor := range node.Neighbors {
        newNode.Neighbors = append(newNode.Neighbors, dfs(neighbor, visited))
    }
    return newNode
}